package com.buddy.learn.algorithm.simple;

import java.util.Stack;

/**
 * @author Buddy
 * @date 2021/4/21
 */
public class _反转链表 {

    /**
     * 使用 stack 栈 反转链表
     *
     * @param head 头节点
     * @return 新的头节点
     */
    private static ListNode reverseListWithStack(ListNode head) {
        if (head == null) {
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

//        ListNode newHead = null;
        ListNode root = null;
        if (!stack.empty()) {
            head = stack.pop();
            root = head;
        }
        while (!stack.empty()) {
            root.next = stack.pop();
            root = root.next;
        }
        root.next = null;
        return head;
    }
    public ListNode reverseList(ListNode head) {
        ListNode pre = null,curr = head,next = null;
        while(curr!= null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;

    }

    private static ListNode reverseListStack(ListNode head) {
        if (head == null) {
            return null;
        }
        //当前结点
        ListNode currNode = head;
        //最后的新节点
        ListNode newNode = null;
        //前一个节点
        ListNode preNode = null;
        while (currNode != null) {
            ListNode next = currNode.next;
            if (next == null) {
                //当下一个节点为空，当前节点就是新的头结点
                newNode = currNode;
            }
            //不空的话，就让当前节点的下一个节点指向前一个节点
            currNode.next = preNode;
            //前一个节点等于当前节点
            preNode = currNode;
            //当前结点等于下一个节点
            currNode = next;
        }
        return newNode;
    }


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        ListNode f = new ListNode(6);
        head.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;

//        ListNode re = reverseListWithStack(head);
        ListNode result = reverseListStack(head);
        while (result != null) {
            System.out.print(result.data + " ");
            result = result.next;
        }
    }


    private static class ListNode {
        int data;
        ListNode next;

        ListNode(int data) {
            this.data = data;
        }
    }
}
